package com.example.demo.algorithms;

import lombok.extern.slf4j.Slf4j;

import java.util.Arrays;

/**
 * <p>Description: </p>
 *
 * @author Eric Lee
 * @version v1.0.0
 * @since 2021/3/16 21:13
 **/
@Slf4j
public class Topk {

    public static void main(String[] args) {
        int[] a = {1, 5, 8, 11};
        int[] b = {2, 4, 6, 7};
        int result = find_kth(a, b, 8);
        System.out.println(result);
    }

    public static int min(int a, int b) {
        return a <= b ? a : b;
    }

    /**
     * 二分思想
     * 先比较num1数组的第k/2个和num2数组的第k/2个元素
     * 情况1：
     * 假如数组1的k/2下标元素 小于 数组2的k/2下标元素 那么说明，数组1的前k/2个元素在合并后数组前K个值里面
     * 此时我们已经找到了合并后数组的前k/2个值，剩下k/2个值在 数组1的【k/2，m】和数组2整个中去找
     * 因为a数组缩小，所以K值也缩小为K-k/2，但是这里的k/2不一定是K值的一半，有一种数组长度小于k/2的情况
     * 需要考虑，这时候我们将不再使用k/2而是数组的长度。
     * 以此产生递归思想，每次修改K为k/2即可，且数组的搜索范围也需要改。
     * 情况2：
     * 与情况一相反，假如数组1的k/2下标元素 大于 数组2的k/2下标元素
     * 时间复杂 o（log（n+m））  TOP-K-FREQUENT
     *
     * @param S
     * @param T
     * @param k
     * @return
     */
    public static int find_kth(int[] S, int[] T, int k) {
        //假定第一个数组长度小
        log.info("第{}小,数组S:{}和T{}", k, S, T);
        if (S.length > T.length) {
            return find_kth(T, S, k);
        }
        if (S.length == 0) {
            return T[k - 1];
        }
        if (k == 1) {
            return min(S[0], T[0]);
        }
        /* 如果两个数组大小不到k/2 取自身大小*/
        int minS = min(S.length, k / 2);
        int minT = min(T.length, k / 2);

        if (S[minS - 1] < T[minT - 1]) {
            int[] rightS = Arrays.copyOfRange(S, minS, S.length);    // 用S右边
            return find_kth(rightS, T, k - minS);
        } else {
            int[] rigthT = Arrays.copyOfRange(T, minT, T.length);   //用T右边
            return find_kth(S, rigthT, k - minT);
        }
    }


}
